import java.util.Arrays;  // 导入Arrays类，用于数组排序
import java.util.Scanner; // 导入Scanner类，用于接收用户输入

public class SequenceList {
    // 顺序表属性
    private int[] data;   // 用于存储顺序表元素的数组
    private int length;   // 记录顺序表当前长度（实际元素个数）
    private int capacity; // 记录顺序表的总容量
    // 构造函数：初始化顺序表
    public SequenceList(int capacity) {
        this.capacity = capacity;      // 设置顺序表容量
        this.data = new int[capacity]; // 创建指定容量的数组
        this.length = 0;               // 初始长度为0（空表）
    }
    // 1. 创建顺序表
    public void createList(int[] elements) {
        // 检查输入元素数量是否超过顺序表容量
        if (elements.length > capacity) {
            System.out.println("输入元素数量超过顺序表容量！");
            return; // 提前结束方法
        }
        // 将输入的元素复制到顺序表中
        System.arraycopy(elements, 0, data, 0, elements.length);
        length = elements.length; // 更新顺序表长度
        sort(); // 创建后自动排序
        System.out.println("创建成功！当前顺序表所有元素：" + this);
    }
    // 2. 插入元素到指定位置
    public void insert(int position, int element) {
        // 检查插入位置是否合法（1到length+1之间）
        if (position < 1 || position > length + 1) {
            System.out.println("插入位置不合法！");
            return;
        }
        // 检查顺序表是否已满
        if (length == capacity) {
            System.out.println("顺序表已满，无法插入！");
            return;
        }
        // 从后向前移动元素，为新元素腾出位置
        for (int i = length; i >= position; i--) {
            data[i] = data[i - 1]; // 每个元素向后移动一位
        }
        data[position - 1] = element; // 在指定位置插入新元素
        length++;                     // 顺序表长度加1
        System.out.println("插入成功！！！当前顺序表所有元素：" + this);
    }
    // 3. 删除指定位置的元素
    public void delete(int position) {
        // 检查删除位置是否合法（1到length之间）
        if (position < 1 || position > length) {
            System.out.println("删除位置不合法！");
            return;
        }
        // 从前向后移动元素，覆盖要删除的元素
        for (int i = position; i < length; i++) {
            data[i - 1] = data[i]; // 每个元素向前移动一位
        }
        length--; // 顺序表长度减1
        System.out.println("删除成功！！！当前顺序表所有元素：" + this);
    }
    // 4. 顺序查找（线性查找）
    public int sequentialSearch(int key) {
        // 遍历顺序表中的每个元素
        for (int i = 0; i < length; i++) {
            if (data[i] == key) {  // 如果找到匹配的元素
                return i + 1;      // 返回位置（从1开始计数）
            }
        }
        return -1; // 未找到返回-1
    }
    // 5. 折半查找（二分查找，要求顺序表有序）
    public int binarySearch(int key) {
        int low = 0;           // 设置查找范围的下界
        int high = length - 1; // 设置查找范围的上界

        // 当查找范围有效时循环
        while (low <= high) {
            int mid = (low + high) / 2; // 计算中间位置
            if (data[mid] == key) {     // 如果中间元素正好是要找的
                return mid + 1;         // 返回位置（从1开始计数）
            } else if (data[mid] < key) { // 如果中间元素小于要找的
                low = mid + 1;           // 调整下界
            } else {                    // 如果中间元素大于要找的
                high = mid - 1;         // 调整上界
            }
        }
        return -1; // 未找到返回-1
    }
    // 6. 倒置顺序表
    public void reverse() {
        // 交换前半部分和后半部分的元素
        for (int i = 0; i < length / 2; i++) {
            // 交换data[i]和data[length-1-i]
            int temp = data[i];
            data[i] = data[length - 1 - i];
            data[length - 1 - i] = temp;
        }
        System.out.println("倒置成功！当前顺序表所有元素：" + this);
    }
    // 7. 输出顺序表内容（重写toString方法）
    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder(); // 使用StringBuilder高效拼接字符串
        // 遍历顺序表中的每个元素
        for (int i = 0; i < length; i++) {
            sb.append(data[i]); // 添加当前元素
            // 如果不是最后一个元素，添加两个空格作为分隔
            if (i < length - 1) {
                sb.append("  ");
            }
        }
        return sb.toString(); // 返回拼接好的字符串
    }
    // 8. 清空顺序表
    public void clear() {
        length = 0; // 只需将长度设为0，逻辑上清空顺序表
        System.out.println("顺序表已清空！");
    }
    // 9. 排序顺序表（使用Arrays.sort方法）
    public void sort() {
        Arrays.sort(data, 0, length); // 对data数组从0到length-1进行排序
        System.out.println("排序成功！！！当前顺序表所有元素：" + this);
    }
    // 主程序入口
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); // 创建Scanner对象接收用户输入
        SequenceList list = null; // 声明顺序表变量，初始为null
        // 主循环，持续显示菜单直到用户选择退出
        while (true) {
            // 打印菜单选项（与图片完全一致）
            System.out.println("\n1. 创建\n2. 插入\n3. 删除\n4. 顺序查找\n5. 折半查找\n6. 倒置\n7. 输出\n8. 清空\n9. 排序\n0. 返回");
            System.out.print("请选择你的操作：");
            int choice = scanner.nextInt(); // 读取用户选择
            // 根据用户选择执行相应操作
            switch (choice) {
                case 1: // 创建顺序表
                    System.out.print("请输入要创建的顺序表长度：");
                    int len = scanner.nextInt();
                    System.out.print("请输入" + len + "个数（空格隔开，可无序输入）：");
                    int[] elements = new int[len];
                    for (int i = 0; i < len; i++) {
                        elements[i] = scanner.nextInt();
                    }
                    // 创建顺序表对象，容量比需求稍大一些
                    list = new SequenceList(len + 10);
                    list.createList(elements);
                    break;
                case 2: // 插入元素
                    if (list == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    System.out.print("请输入要插入的位置（从1开始）及元素：");
                    int pos = scanner.nextInt();
                    int elem = scanner.nextInt();
                    list.insert(pos, elem);
                    break;
                case 3: // 删除元素
                    if (list == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    System.out.print("请输入要删除的位置（从1开始）：");
                    int delPos = scanner.nextInt();
                    list.delete(delPos);
                    break;
                case 4: // 顺序查找
                    if (list == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    System.out.print("请输入要查找的元素：");
                    int seqKey = scanner.nextInt();
                    int seqResult = list.sequentialSearch(seqKey);
                    if (seqResult != -1) {
                        System.out.println("元素 " + seqKey + " 位于第 " + seqResult + " 个位置");
                    } else {
                        System.out.println("未找到元素 " + seqKey);
                    }
                    break;
                case 5: // 折半查找
                    if (list == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    System.out.print("请输入要查找的元素：");
                    int binKey = scanner.nextInt();
                    int binResult = list.binarySearch(binKey);
                    if (binResult != -1) {
                        System.out.println("元素 " + binKey + " 位于第 " + binResult + " 个位置");
                    } else {
                        System.out.println("未找到元素 " + binKey);
                    }
                    break;
                case 6: // 倒置顺序表
                    if (list == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    list.reverse();
                    break;
                case 7: // 输出顺序表
                    if (list == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    System.out.println("当前顺序表所有元素：" + list);
                    break;
                case 8: // 清空顺序表
                    if (list == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    list.clear();
                    break;
                case 9: // 排序顺序表
                    if (list == null) {
                        System.out.println("请先创建顺序表！");
                        break;
                    }
                    list.sort();
                    break;
                case 0: // 退出程序
                    System.out.println("程序结束！");
                    scanner.close(); // 关闭Scanner
                    return;         // 结束程序
                default: // 无效输入处理
                    System.out.println("无效的选择，请重新输入！");
            }
        }
    }
}